import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-09-28
 * Time: 22:24
 */

public class Solution {
//     排序 + 双指针
//     我们记录的是哪个区间会给这个元素发送
//     因为一个元素只会给比他小的元素, 也就是说一个元素只能接收到比他大的元素的请求
//     所以排过序之后, 这个区间只会右移, 这样保证了时间复杂度是 O (N)
//     怎么保证相同的元素能够相互发送呢 ?
//     区间左端点不变, 相同的元素的区间的左端点是相同的, 这就是下面为什么使用的是 &&
    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int n = ages.length, ans = 0;
        for (int k = 0, start = 0, end = 0; k < n; k++) {
            // 为什么这里面是 &&,  因为数组里面由重复元素, 那么元素是可以给相等的元素发送的
            // 此时可能相等的元素在这个元素的前面, 但是该元素又要给这个元素发送, 所以是满足条件的, 因此当这两个条件都不满足的时候才不发送
            while (start < k && !check(ages[start], ages[k])) start++;
            if (end < k) end = k;
            while (end < n && check(ages[end], ages[k])) end++;
            // 注意要判断 end > start 才 +, 因为可能 end = start, 此时再 -1, 就为 -1 了
            // 这里为什么要 -1, 因为 start 是从元素本身开始的, 但是元素不能给自己发请求的, 所以要减去
            if (end > start) ans += end - start - 1;
        }
        return ans;
    }
    boolean check(int x, int y) {
        if (y <= 0.5 * x + 7) return false;
        if (y > x) return false;
        if (y > 100 && x < 100) return false; // 这个判断可以不要, 因为这种情况 下 y > x 是一定的
        return true;
    }


    /**
     *  方法二:
     *  计数排序 + 前缀和
     *  排过序之后, 这个区间只会右移, 这样保证了时间复杂度是 O (N)
     *  相同的值只计算一个, 然后 * 元素个数
     */
    public int numFriendRequests2(int[] ages) {
        int ans = 0;
        int[] arr = new int[121];
        int len = ages.length;
        for (int i = 0; i < len; i++) {
            arr[ages[i]]++;
        }
        int[] prefix = new int[121];
        prefix[0] = 0;
        for (int i = 1; i < 121; i++) {
            prefix[i] = prefix[i-1] + arr[i];
        }
        for (int i = 1; i < 121; i++) {
            if (arr[i] != 0) {
                int start = i;
                while (start < 121 && !judge(start, i)) {
                    start++;
                }
                int end = start;
                while (end < 121 && judge(end, i)) {
                    end++;
                }
                if (end > start) {
                    // 注意前缀和包含了当前值, 所以要用前一个下标, 同时这里将元素本身算进去了, 所以要除去
                    // 同时, 相同的值发送的请求的个数是相同的, 所以 * 元素个数
                    ans += (prefix[end-1] - prefix[i-1] - 1) * arr[i];
                }
            }
        }
        return ans;
    }

    private boolean judge(int valueX, int valueY) {
        if (valueY <= valueX/2 + 7) {
            return false;
        }
        return valueY <= valueX;
    }
}
